//! A doubly linked list-based queue implementation in Rust.
//! This module provides a generic queue that supports operations at both ends.

use std::ptr;

/// A node in the doubly linked list.
struct Node<T> {
    value: T,
    next: *mut Node<T>,
    prev: *mut Node<T>,
}

/// A doubly linked list-based queue.
pub struct Queue<T> {
    head: *mut Node<T>,
    tail: *mut Node<T>,
}

impl<T> Queue<T> {
    /// Creates a new empty queue.
    pub fn new() -> Self {
        Queue {
            head: ptr::null_mut(),
            tail: ptr::null_mut(),
        }
    }

    /// Checks if the queue is empty.
    pub fn is_empty(&self) -> bool {
        self.head.is_null()
    }

    /// Pushes a value to the head of the queue.
    pub fn push_head(&mut self, value: T) {
        let new_node = Box::into_raw(Box::new(Node {
            value,
            next: self.head,
            prev: ptr::null_mut(),
        }));

        if !self.head.is_null() {
            unsafe {
                (*self.head).prev = new_node;
            }
        } else {
            self.tail = new_node;
        }

        self.head = new_node;
    }

    /// Pushes a value to the tail of the queue.
    pub fn push_tail(&mut self, value: T) {
        let new_node = Box::into_raw(Box::new(Node {
            value,
            next: ptr::null_mut(),
            prev: self.tail,
        }));

        if !self.tail.is_null() {
            unsafe {
                (*self.tail).next = new_node;
            }
        } else {
            self.head = new_node;
        }

        self.tail = new_node;
    }

    /// Pops a value from the head of the queue.
    pub fn pop_head(&mut self) -> Option<T> {
        if self.head.is_null() {
            None
        } else {
            unsafe {
                let node = Box::from_raw(self.head);
                self.head = node.next;

                if !self.head.is_null() {
                    (*self.head).prev = ptr::null_mut();
                } else {
                    self.tail = ptr::null_mut();
                }

                Some(node.value)
            }
        }
    }

    /// Pops a value from the tail of the queue.
    pub fn pop_tail(&mut self) -> Option<T> {
        if self.tail.is_null() {
            None
        } else {
            unsafe {
                let node = Box::from_raw(self.tail);
                self.tail = node.prev;

                if !self.tail.is_null() {
                    (*self.tail).next = ptr::null_mut();
                } else {
                    self.head = ptr::null_mut();
                }

                Some(node.value)
            }
        }
    }

    /// Peeks at the value at the head of the queue.
    pub fn peek_head(&self) -> Option<&T> {
        if self.head.is_null() {
            None
        } else {
            unsafe { Some(&(*self.head).value) }
        }
    }

    /// Peeks at the value at the tail of the queue.
    pub fn peek_tail(&self) -> Option<&T> {
        if self.tail.is_null() {
            None
        } else {
            unsafe { Some(&(*self.tail).value) }
        }
    }
}

impl<T> Drop for Queue<T> {
    fn drop(&mut self) {
        while let Some(_) = self.pop_head() {}
    }
}

#[cfg(test)]
mod tests {
    use super::Queue;

    #[test]
    fn test_queue_new_free() {
        let mut queue: Queue<i32> = Queue::new();
        assert!(queue.is_empty());

        for _ in 0..1000 {
            queue.push_head(1);
        }

        drop(queue);
    }

    #[test]
    fn test_queue_push_head() {
        let mut queue: Queue<i32> = Queue::new();

        for _ in 0..1000 {
            queue.push_head(1);
            queue.push_head(2);
            queue.push_head(3);
            queue.push_head(4);
        }

        assert!(!queue.is_empty());

        for _ in 0..1000 {
            assert_eq!(queue.pop_tail(), Some(1));
            assert_eq!(queue.pop_tail(), Some(2));
            assert_eq!(queue.pop_tail(), Some(3));
            assert_eq!(queue.pop_tail(), Some(4));
        }

        for _ in 0..1000 {
            assert_eq!(queue.pop_head(), Some(4));
            assert_eq!(queue.pop_head(), Some(3));
            assert_eq!(queue.pop_head(), Some(2));
            assert_eq!(queue.pop_head(), Some(1));
        }
    }

    #[test]
    fn test_queue_pop_head() {
        let mut queue: Queue<i32> = Queue::new();
        assert_eq!(queue.pop_head(), None);

        for _ in 0..1000 {
            queue.push_head(1);
            queue.push_head(2);
            queue.push_head(3);
            queue.push_head(4);
        }

        for _ in 0..1000 {
            assert_eq!(queue.pop_head(), Some(4));
            assert_eq!(queue.pop_head(), Some(3));
            assert_eq!(queue.pop_head(), Some(2));
            assert_eq!(queue.pop_head(), Some(1));
        }

        assert_eq!(queue.pop_head(), None);
    }

    #[test]
    fn test_queue_peek_head() {
        let mut queue: Queue<i32> = Queue::new();
        assert_eq!(queue.peek_head(), None);

        for _ in 0..1000 {
            queue.push_head(1);
            queue.push_head(2);
            queue.push_head(3);
            queue.push_head(4);
        }

        for _ in 0..1000 {
            assert_eq!(queue.peek_head(), Some(&4));
            assert_eq!(queue.pop_head(), Some(4));
            assert_eq!(queue.peek_head(), Some(&3));
            assert_eq!(queue.pop_head(), Some(3));
            assert_eq!(queue.peek_head(), Some(&2));
            assert_eq!(queue.pop_head(), Some(2));
            assert_eq!(queue.peek_head(), Some(&1));
            assert_eq!(queue.pop_head(), Some(1));
        }

        assert_eq!(queue.peek_head(), None);
    }

    #[test]
    fn test_queue_push_tail() {
        let mut queue: Queue<i32> = Queue::new();

        for _ in 0..1000 {
            queue.push_tail(1);
            queue.push_tail(2);
            queue.push_tail(3);
            queue.push_tail(4);
        }

        assert!(!queue.is_empty());

        for _ in 0..1000 {
            assert_eq!(queue.pop_head(), Some(1));
            assert_eq!(queue.pop_head(), Some(2));
            assert_eq!(queue.pop_head(), Some(3));
            assert_eq!(queue.pop_head(), Some(4));
        }

        for _ in 0..1000 {
            assert_eq!(queue.pop_tail(), Some(4));
            assert_eq!(queue.pop_tail(), Some(3));
            assert_eq!(queue.pop_tail(), Some(2));
            assert_eq!(queue.pop_tail(), Some(1));
        }
    }

    #[test]
    fn test_queue_pop_tail() {
        let mut queue: Queue<i32> = Queue::new();
        assert_eq!(queue.pop_tail(), None);

        for _ in 0..1000 {
            queue.push_head(1);
            queue.push_head(2);
            queue.push_head(3);
            queue.push_head(4);
        }

        for _ in 0..1000 {
            assert_eq!(queue.pop_tail(), Some(1));
            assert_eq!(queue.pop_tail(), Some(2));
            assert_eq!(queue.pop_tail(), Some(3));
            assert_eq!(queue.pop_tail(), Some(4));
        }

        assert_eq!(queue.pop_tail(), None);
    }

    #[test]
    fn test_queue_peek_tail() {
        let mut queue: Queue<i32> = Queue::new();
        assert_eq!(queue.peek_tail(), None);

        for _ in 0..1000 {
            queue.push_head(1);
            queue.push_head(2);
            queue.push_head(3);
            queue.push_head(4);
        }

        for _ in 0..1000 {
            assert_eq!(queue.peek_tail(), Some(&1));
            assert_eq!(queue.pop_tail(), Some(1));
            assert_eq!(queue.peek_tail(), Some(&2));
            assert_eq!(queue.pop_tail(), Some(2));
            assert_eq!(queue.peek_tail(), Some(&3));
            assert_eq!(queue.pop_tail(), Some(3));
            assert_eq!(queue.peek_tail(), Some(&4));
            assert_eq!(queue.pop_tail(), Some(4));
        }

        assert_eq!(queue.peek_tail(), None);
    }

    #[test]
    fn test_queue_is_empty() {
        let mut queue: Queue<i32> = Queue::new();
        assert!(queue.is_empty());

        queue.push_head(1);
        assert!(!queue.is_empty());

        queue.pop_head();
        assert!(queue.is_empty());

        queue.push_tail(1);
        assert!(!queue.is_empty());

        queue.pop_tail();
        assert!(queue.is_empty());
    }
}
